package sort;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Random;

import org.junit.Test;

public class QuickSort {

    /**
     * 首先这是
     * 荷兰国旗 问题
     * <= p 的值 放在 左边 ，大于 p 的值 在 右边
     * 并且 要求  划分值 p在  **左边区域 ** 的   最右边的位置
     * 在当前的 题目 当中 这里的 p值 就是 arr[N - 1]
     */
    public static void function(int arr[]) {
        int N = arr.length;
        int left = -1;
        int index = 0;
        while (index < N) {
            // 如果 条件 成立 直接 交换  currentValue 与 left + 1 位置的值
            if (arr[index] <= arr[N - 1])
                swap(arr, ++left, index++);
            else
                index++;
        }
    }

    /**
     * 荷兰国旗的升级问题
     * <p left
     * = p 在中间
     * > p 在右边
     * 这里的
     * while(index < r)
     * 就行
     * index <= r 这是不对的  针对上面的   那个 低级版本的
     * 荷兰过期 版本 就行
     */

    public static int[] func(int arr[]) {
//		int ans [] = new int [2];
        int l = -1;
        int r = arr.length - 1;
        int N = r;
        int index = 0;
        while (index < r) {
            if (arr[index] < arr[N])
                swap(arr, ++l, index++);
            else if (arr[index] == arr[N])
                index++;
            else
                swap(arr, index, --r);
        }
        swap(arr, r++, N);
        return new int[]{l + 1, r};
    }

    /**
     * 快排
     * l 是 < 的边界: 就是 < p 的最右边的 下标
     * r 是 > 的边界: >p 的最左边的下标
     *
     */
    public static void quickSort(int arr[]) {
        int l = 0;
        int r = arr.length - 1;
        process(arr, l, r);
    }

    /**
     * 黑盒 过程
     */
    public static void process(int arr[], int l, int r) {
        if (l >= r)
            return;

        swap(arr, r, l + (int) (Math.random() * (r - l + 1)));
//		int temp [] = netherlandsFlag(arr,l,r);
        int temp[] = partion(arr, l, r);
        process(arr, l, temp[0]);
        process(arr, temp[1], r);
    }


    public static int[] netherlandsFlag(int[] arr, int L, int R) {
//		if (L > R) {
//			return new int[] { -1, -1 };
//		}
//		if (L == R) {
//			return new int[] { L, R };
//		}
        int less = L - 1;
        int more = R;
        int index = L;
        while (index < more) {
            if (arr[index] == arr[R]) {
                index++;
            } else if (arr[index] < arr[R]) {
                swap(arr, index++, ++less);
            } else {
                swap(arr, index, --more);
            }
        }
        swap(arr, more, R);
		/*
		 这里 有问题 啊！
		为什么 more + 1， 和 more  为什么全部都是正确的 ？
		这里解释一下：
		因为 如果 more 不加 1 的话，只是 把 相等区域的 一个 元素element 划到了 >(大于) 的区域而已, 但是这样对整个 排序没有任何的影响
		所以 more 和 more + 1 都是正确 的
		 */
        return new int[]{less, more + 1};
    }


    public static int[] partion(int[] nums, int l, int r) {
        int less = l - 1, index = l, more = r;
        while (index < more) {
            if (nums[index] < nums[r]) {
                swap(nums, ++less, index++);
            } else if (nums[index] == nums[r]) {
                index++;
            } else {
                swap(nums, --more, index);
            }
        }
        // 把 more 与 r 位置 进行交换， 这点别忘了
        swap(nums, more, r);
        /*
		 这里 有问题 啊！
		为什么 more + 1， 和 more  为什么全部都是正确的 ？
		这里解释一下：
		因为 如果 more 不加 1 的话，只是 把 相等区域的 一个 元素element 划到了 >(大于) 的区域而已, 但是这样对整个 排序没有任何的影响
		所以 more 和 more + 1 都是正确 的
		 */
        return new int[]{less, more};
    }


    public static void swap(int arr[], int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }


    public static void main(String[] args) {
        int arr[] = {};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    @Test
    public void test() {
        int arr[] = {4, 5, 8, 7, 7, 3, 2, 6, 8, 7};
        System.out.println(Arrays.toString(netherlandsFlag(arr, 0, arr.length - 1)));
        System.out.println(Arrays.toString(arr));
    }


    /**
     * 首先生成 随机数组的函数！
     *
     * @param arraySize 数组的大小（根据 题目的 不同， 也可能是 一个数组的  最大长度， 随机生成 数组的 长度 在 1 ~  arraySize 之间）
     * @param max       数组中元素的最大值
     * @param min       一个指标， 如果 min = 0， 代表 数组中的元素，>=0 ，min = 1， 代表 全是正数  min = -1 ，可正 ke 负 ， 可为 0
     * @param fix       如果 fix = true 代表， 数组的长度 固定， 反之， 数组的长度 不固定
     * @return 一个 生成的随机的数组(长度可以随机， 也可以 固定， 看具体题目的要求)
     */
    public int[] ramdomArray(int arraySize, int max, int min, boolean fix) {
        int ramdomArraySize = fix ? arraySize : (int) (Math.random() * (arraySize + 1)); // 数组的长度 , 由fix 来控制 是否随机
        int arr[] = new int[ramdomArraySize];
        if (min == 0) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1)); // arr[i] = [0 , max]
            }
        } else if (min == 1) {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max)) + 1;//  arr[i] =  [1 , max + 1)
            }
        } else {
            for (int i = 0; i < ramdomArraySize; i++) {
                arr[i] = (int) (Math.random() * (max + 1) - Math.random() * (max + 1)); // 可正 可 负 可为 0
            }
        }
        return arr;
    }


    public void testRight() {
        int testTimes = 1000_000; // 自己写！
        int arraySize = 100;
        int max = 20;
        int min = -1;
        boolean fix = false;
        boolean isSuccess = true;
        for (int i = 0; i < testTimes; i++) {
            int[] ints = ramdomArray(arraySize, max, min, fix);
            int arr1[] = Arrays.copyOf(ints, ints.length);
            int arr2[] = Arrays.copyOf(ints, ints.length);
            // 你的方法
            quickSort(arr1);
//			arr1[0] = 10;
//			System.out.println(Arrays.toString(arr1));
//			absoluteRightFunction(arr2);
            Arrays.sort(arr2);
            if (!Arrays.equals(arr1, arr2)) {
                 /*
                  说明 有问题， 可以打印下，数组，看下是什么 问题！
                  */
                isSuccess = false;
                System.out.println(Arrays.toString(ints));
//				break; // 找到一组， 数组就行，如果一组， debug 不出来， 那就 多打印 几组， 或者 收集 在一个 collection 里面也可以！
            }
        }
        System.out.println(isSuccess ? "success" : "fuck!");
    }

    @Test
    public void testNew() {
        testRight();
    }


    @Test
    public void test2(){
//        int nums[]= {5,6,4,3,2,1};
        int nums[]= {5,6,2,0,1,-4,3,2,1};
        new My().sort(nums,0,nums.length - 1);
//        quickSort(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println(Integer.toBinaryString(-6));


        Integer a = 19;
        Integer b = 19;
        System.out.println(a == b);

    }

}
class My{

    public int[] paration(int nums[],int l,int r){
        int left = l - 1, right = r,index = l;
        while(index < right){
            if(nums[index] < nums[r]){
                swap(nums,++left,index++);
            }else if(nums[index] == nums[r]){
                index++;
            }else{
                swap(nums,index,--right);
            }
        }

        swap(nums,right++,r);
        return new int[]{left,right};
    }


    /*
     练手的测试代码，没有问题
     */
    public int[] f(int nums[],int l,int r){
        int less  = l - 1, more = r,index = l;
        while(index < more){
            if(nums[index] < nums[r]){ //
                swap(nums,++less,index++);
            }else if(nums[index] == nums[r]){
                index++;
            }else{
                swap(nums,--more,index);
            }
        }
        swap(nums,more++,r);
        return new int[]{less,more};
    }


    public static void swap(int nums[], int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void sort(int nums[],int l,int r){
        if(l >= r){  // 这里一定 要是 >= , 相等直接返回就不用说了 ,因为 会存在 l > r 的情况, 特殊情况的边界是存在的
            return ;
        }
        int ran = new Random().nextInt(r - l + 1);
        swap(nums,l + ran,r);
//        swap(nums, r, l + (int) (Math.random() * (r - l + 1)));
        int partation[] = f(nums,l,r);
        sort(nums,l,partation[0]);
        sort(nums,partation[1],r);
//        ArrayDeque<Integer> quque = new ArrayDeque<>();
//        quque.remove();
//        quque.add()
    }

    public void f(int a,String b){

    }
    public int f(String b,int a){
        return 0;
    }



}
abstract class F{
    static {

    }
    public F(){

    }
}